import java.util.*;

/**
 * 1019. 链表中的下一个更大节点
 * https://leetcode-cn.com/problems/next-greater-node-in-linked-list/
 */
public class Solutions_1019 {
    public static void main(String[] args) {
//        int[] nums = {2, 1, 5};  // output: {5, 5, 0}
//        int[] nums = {2, 7, 4, 3, 5};  // output: {7, 0, 5, 5, 0}
        int[] nums = {1, 7, 5, 1, 9, 2, 5, 1};  // output: {7, 9, 9, 9, 0, 5, 0, 0}

        ListNode head = MyLinkedListUtils.ArrayToListNode(nums);
        int[] result = nextLargerNodes(head);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 解法二：数组形式实现单调栈（3ms）
     * 关键点：保证链表的索引（链表是没有索引的）对应 res 结果数组的索引
     * 创建一个栈：用于存储链表的结点在 list 列表上的索引，就可以通过弹栈的索引来获取/修改对应的元素
     * 创建一个列表：用于存储链表的结点值，其索引存储在 stack 中
     */
    public static int[] nextLargerNodes(ListNode head) {
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len ++;
            cur = cur.next;
        }
        // 记录数组元素，若找到某元素的下一更大元素，那么就修改元素为下一更大元素
        int[] res = new int[len];
        int[] stack = new int[len];
        int i = 0, j = 0;
        cur = head;
        while (cur != null) {
            while (j > 0 && cur.val > res[stack[j - 1]]) {
                // 弹栈操作
                res[stack[j - 1]] = cur.val;
                j --;
            }
            // 记录元素，并记录索引
            res[i] = cur.val;
            stack[j] = i;
            i++;
            j++;
            cur = cur.next;
        }
        while (j > 0) {
            // 栈中还有元素时，那么 res 数组中 stack[j - 1] 索引上的元素，没有下一个更大的元素
            res[stack[j - 1]] = 0;
            j --;
        }
        return res;
    }

    /**
     * 解法一：单调栈（22ms）
     * 关键点：保证链表的索引（链表是没有索引的）对应 res 结果数组的索引
     * 创建一个栈：用于存储链表的结点在 list 列表上的索引，就可以通过弹栈的索引来获取/修改对应的元素
     * 创建一个列表：用于存储链表的结点值，其索引存储在 stack 中
     */
    public static int[] nextLargerNodes2(ListNode head) {
        if (head == null) {
            return new int[0];
        }
        if (head.next == null) {
            return new int[]{0};
        }
        List<Integer> list = new ArrayList<>();
        Deque<Integer> stack = new LinkedList<>();
        ListNode cur = head;
        while (cur != null) {
            while (!stack.isEmpty() && cur.val > list.get(stack.peek())) {
                // head.val 就是 list.get(stack.peek()) 中的下一个更大元素
                list.set(stack.pop(), cur.val);
            }
            // list 记录值
            list.add(cur.val);
            // stack 记录值在 list 中的索引
            stack.push(list.size() - 1);
            cur = cur.next;
        }
        // 最终 stack 中的索引上的元素，即是没有弹出的，没有下一个更大元素的元素
        while (!stack.isEmpty()) {
            list.set(stack.pop(), 0);
        }
        // list 列表转换成 int 数组
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}
